﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NetworkSimulator
{
    public abstract class DisjointPaths
    {
        protected Topology map = Topology.instance();

        // Use this to call a node quickly by ID
        protected Dictionary<int, Node> nodes;

        // Use for prevent make change in map while processing
        protected Dictionary<Link, double> usable_bw;
        protected Dictionary<Link, double> using_bw;
        protected Dictionary<Link, double> cost;

        public DisjointPaths()
        {
            nodes = new Dictionary<int, Node>();
            foreach (Node node in map.Nodes)
            {
                nodes[node.Id] = node;
            }
            usable_bw = new Dictionary<Link, double>();
            using_bw = new Dictionary<Link, double>();
            cost = new Dictionary<Link, double>();
            this.Renew();
        }

        protected void Renew()
        {
            foreach (Node node in map.Nodes)
            {
                foreach (Link link in node.Links)
                {
                    usable_bw[link] = link.ResidualBandwidth;
                    using_bw[link] = 0;
                    cost[link] = 1;
                }
            }
        }

        // Get Disjoint Paths for DORA algorithm offline phare
        protected List<Link> GetDisjointPaths(Node source, Node dest)
        {
            Path path = new Path();
            List<Link> link = new List<Link>();
            path = dijkstra(source, dest);
            // Set usable_bw foreach link in result path to remove this link
            foreach (Link l in path.Links)
            {
                usable_bw[l] = 0;
                using_bw[l] = 0;
                link.Add(l);
            }
            return link;
        }

        // Remove links with bandwidth less than bw
        protected void removeLinks(double bw)
        {
            foreach (Node node in map.Nodes)
                foreach (Link link in node.Links)
                    if (link.ResidualBandwidth < bw)
                        usable_bw[link] = 0;
        }

        protected Path BFS(Node source, Node dest)
        {
            Path result_path = new Path();

            Node curNode; // use for browse map

            // queue use for browse from source node to find out dest node
            Queue<Node> queue = new Queue<Node>();

            // tracking use for record browsed link
            Stack<Link> tracking = new Stack<Link>();

            // found or not dest node
            bool found = false;

            // checked node
            Dictionary<Node, bool> checked_node = new Dictionary<Node, bool>();
            foreach (Node node in map.Nodes)
            {
                checked_node.Add(node, false);
            }

            // Add source node to queue
            queue.Enqueue(source);

            // Find out destination node..
            while (queue.Count > 0 && !found)
            {
                curNode = queue.Dequeue();
                foreach (Link link in curNode.Links)
                {
                    if (usable_bw[link] > 0 && !checked_node[link.Destination])
                    {
                        // Track this link
                        tracking.Push(link);

                        if (link.Destination == dest)
                        {
                            found = true;
                            break;
                        }
                        else
                        {
                            // Checked neighbor node
                            checked_node[link.Destination] = true;

                            // Add neighbor to queue
                            queue.Enqueue(link.Destination);
                        }
                    }
                }
            }


            // Get the invert path from tracking
            if (tracking.Count > 0)
            {
                Link now = tracking.Pop();
                Stack<Link> temp = new Stack<Link>();
                temp.Push(now);
                Link next;

                while (tracking.Count > 0)
                {
                    next = tracking.Pop();
                    if (now.Source == next.Destination)
                    {
                        now = next;
                        temp.Push(now);
                    }
                }

                // Get the path from invert path in temp stack
                while (temp.Count > 0)
                {
                    result_path.Links.Add(temp.Pop());
                }
            }
            return result_path;
        }
        
        //============================================================================
        public Path dijkstra(Node source, Node dest)
        {
            Dictionary<Node, double> distance = new Dictionary<Node, double>();
            Dictionary<Node, Node> previous = new Dictionary<Node, Node>();
            List<Node> nodes = new List<Node>();
            // Initialize
            foreach (Node node in map.Nodes)
            {
                distance[node] = double.MaxValue;
                previous[node] = null;
                nodes.Add(node);
            }

            distance[source] = 0;

            while (nodes.Count > 0)
            {
                Node current = nodes[0];
                foreach (Node node in nodes)
                {
                    if (distance[node] < distance[current])
                        current = node;
                }
                nodes.Remove(current);

                foreach (Link link in current.Links)
                {
                    if (usable_bw[link] <= 0)
                        continue;

                    Node neighbor = link.Destination;
                    if (distance[neighbor] > distance[current] + cost[link])
                    {
                        distance[neighbor] = distance[current] + cost[link];
                        previous[neighbor] = current;
                    }
                }
            }

            // Get path
            Node destination = dest;
            Node pointer = previous[destination];
            Path result = new Path();
            while (destination != source)
            {
                foreach (Link link in pointer.Links)
                {
                    if (link.Destination == destination)
                    {
                        result.Add(link);
                        destination = previous[destination];
                        pointer = previous[destination];
                        break;
                    }
                }
            }
            if (!result.isEmpty())
                result.Reverse();

            return result;
        }
    }
}
